/*
https://leetcode.cn/problems/number-of-different-subsequences-gcds/solutions/2060230/xu-lie-zhong-bu-tong-zui-da-gong-yue-shu-ha1j/
 */
import java.util.Arrays;

public class Solution1819 {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int max= Arrays.stream(nums).max().getAsInt();
        int[] occupy=new int[max+1];
        for (int num : nums) {
            occupy[num]=1;
        }
        int ans=0;
        for (int i=1;i<=max;i++){
            int temp=0;
            for (int j=i;j<=max;j+=i){
                if (occupy[j]==1){
                    temp=temp==0?j:gcd(temp,j);
                }
            }
            if (temp==i){
                ans++;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        if (a<b){
            int t=a;
            a=b;
            b=t;
        }
        return a%b==0?b:gcd(b,a%b);
    }

    public static void main(String[] args) {
        System.out.println(new Solution1819().countDifferentSubsequenceGCDs(new int[]{6,10,3}));
    }
}
